package 板子;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 费用流板子 {
	
	public static void main(String []args) {
		int arr[] []= new int [4][];
		System.out.println(arr.length);
		System.out.println(arr[0].length);
	}
	
	
	/**
	 * open eyes
	 * 这里的 二维数组  的列 直接   **缺省**
	 * 下面 其实 也很好理解
	 *  二维数组 arr[][]
	 *  其中arr[0] 存储的 是一个 一维数组的引用(4个字节),
	 *  所以 这个 arr[i] 表示的一维数组  的细节 可以是不一样的
	 *  比如, 典型的 就是 arr[0] , 和 arr[1] 表示的 数组的 长度可以是不一致的!
	 *  就如下面的 代码所示!
	 */
	public void test() {
		int [][]arr=new int[3][];
		//第一行
		arr[0]=new int[7];//相当于int[] a=new int[3]
		for(int i=0;i<arr[0].length;i++){
			arr[0][i]=i+1;
		}
		//第二行
		arr[1]=new int[4];
		  for(int i=0;i<arr[1].length;i++){
			  arr[1][i]=i+1;
		  }
		//第三行
			arr[2]=new int[8];
			  for(int i=0;i<arr[2].length;i++){
				  arr[2][i]=i+1;
			  }
		//遍历数组
			for(int i=0;i<arr.length;i++){
				  for(int j=0;j<arr[i].length;j++){
					  System.out.print(arr[i][j]);
				  }
				  System.out.println();
			  }
	}
	

}

/**
 * 研究一下这个代码的 细节！
 * 尤其是 图  表示 相关的 
 */
class OtherSolution {
	public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
		int n = robot.size();
		int m = factory.length;
		List<Edge> es = new ArrayList<>();
		int src = n+m, sink = src + 1;
		for(int i = 0;i < n;i++){
			es.add(new Edge(src, i, 1, 0));
			for(int j = 0;j < m;j++){
				es.add(new Edge(i, n+j, 1, Math.abs(robot.get(i) - factory[j][0])));
			}
		}
		for(int j = 0;j < m;j++){
			es.add(new Edge(n+j, sink, factory[j][1], 0));
		}
		return solveMinCostFlow(compileWD(sink+1, es), src, sink, n);
	}

	public class Edge
	{
		public int from, to;
		public int capacity;
		public long cost;
		public int flow;
		public Edge complement;
		// public int iniflow;

		public Edge(int from, int to, int capacity, long cost) {
			this.from = from;
			this.to = to;
			this.capacity = capacity;
			this.cost = cost;
		}

		@Override
		public String toString() {
			return "Edge [from=" + from + ", to=" + to + ", capacity="
					+ capacity + ", cost=" + cost + "]";
		}
	}

	public Edge[][] compileWD(int n, List<Edge> edges)
	{
		Edge[][] g = new Edge[n][];
		// cloning
		for(int i = edges.size()-1;i >= 0;i--){
			Edge origin = edges.get(i);
			Edge clone = new Edge(origin.to, origin.from, origin.capacity, -origin.cost);
			clone.flow = origin.capacity;
			clone.complement = origin;
			origin.complement = clone;
			edges.add(clone);
		}

		int[] p = new int[n];
		for(Edge e : edges)p[e.from]++;
		for(int i = 0;i < n;i++)g[i] = new Edge[p[i]];
		for(Edge e : edges)g[e.from][--p[e.from]] = e;
		return g;
	}

	public long solveMinCostFlow(Edge[][] g, int source, int sink, long all)
	{
		int n = g.length;
		long mincost = 0;
		long[] potential = new long[n];

		final long[] d = new long[n];
		MinHeapL q = new MinHeapL(n);
		while(all > 0){
			// shortest path src->sink
			Edge[] inedge = new Edge[n];
			Arrays.fill(d, Long.MAX_VALUE / 2);
			d[source] = 0;
			q.add(source, 0);
			while(q.size() > 0){
				int cur = q.argmin();
				q.remove(cur);
				for(Edge ne : g[cur]){
					if(ne.capacity - ne.flow > 0){
						long nd = d[cur] + ne.cost + potential[cur] - potential[ne.to];
						if(d[ne.to] > nd){
							inedge[ne.to] = ne;
							d[ne.to] = nd;
							q.update(ne.to, nd);
						}
					}
				}
			}

			if(inedge[sink] == null)break;

			long minflow = all;
			long sumcost = 0;
			for(Edge e = inedge[sink];e != null;e = inedge[e.from]){
				if(e.capacity - e.flow < minflow)minflow = e.capacity - e.flow;
				sumcost += e.cost;
			}
			mincost += minflow * sumcost;
			for(Edge e = inedge[sink];e != null;e = inedge[e.from]){
				e.flow += minflow;
				e.complement.flow -= minflow;
			}

			all -= minflow;
			for(int i = 0;i < n;i++){
				potential[i] += d[i];
			}
		}
		return mincost;
	}

	public class MinHeapL {
		public long[] a;
		public int[] map;
		public int[] imap;
		public int n;
		public int pos;
		public static final long INF = Long.MAX_VALUE;

		public MinHeapL(int m)
		{
			n = Integer.highestOneBit((m+1)<<1);
			a = new long[n];
			map = new int[n];
			imap = new int[n];
			Arrays.fill(a, INF);
			Arrays.fill(map, -1);
			Arrays.fill(imap, -1);
			pos = 1;
		}

		public long add(int ind, long x)
		{
			int ret = imap[ind];
			if(imap[ind] < 0){
				a[pos] = x; map[pos] = ind; imap[ind] = pos;
				pos++;
				up(pos-1);
			}
			return ret != -1 ? a[ret] : x;
		}

		public long update(int ind, long x)
		{
			int ret = imap[ind];
			if(imap[ind] < 0){
				a[pos] = x; map[pos] = ind; imap[ind] = pos;
				pos++;
				up(pos-1);
			}else{
				a[ret] = x;
				up(ret);
				down(ret);
			}
			return x;
		}

		public long remove(int ind)
		{
			if(pos == 1)return INF;
			if(imap[ind] == -1)return INF;

			pos--;
			int rem = imap[ind];
			long ret = a[rem];
			map[rem] = map[pos];
			imap[map[pos]] = rem;
			imap[ind] = -1;
			a[rem] = a[pos];
			a[pos] = INF;
			map[pos] = -1;

			up(rem);
			down(rem);
			return ret;
		}

		public long min() { return a[1]; }
		public int argmin() { return map[1]; }
		public int size() {	return pos-1; }
		public long get(int ind){ return a[imap[ind]]; }

		private void up(int cur)
		{
			//		for(int c = cur, p = c>>>1;p >= 1 && (a[p] > a[c] || a[p] == a[c] && map[p] > map[c]);c>>>=1, p>>>=1){
			for(int c = cur, p = c>>>1;p >= 1 && a[p] > a[c];c>>>=1, p>>>=1){
				long d = a[p]; a[p] = a[c]; a[c] = d;
				int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e;
				e = map[p]; map[p] = map[c]; map[c] = e;
			}
		}

		private void down(int cur)
		{
			for(int c = cur;2*c < pos;){
				//			int b = a[2*c] < a[2*c+1] || a[2*c] == a[2*c+1] && map[2*c] < map[2*c+1] ? 2*c : 2*c+1;
				//			if(a[b] < a[c] || a[b] == a[c] && map[b] < map[c]){
				int b = a[2*c] < a[2*c+1] ? 2*c : 2*c+1;
				if(a[b] < a[c]){
					long d = a[c]; a[c] = a[b]; a[b] = d;
					int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e;
					e = map[c]; map[c] = map[b]; map[b] = e;
					c = b;
				}else{
					break;
				}
			}
		}
	}

}